In the context of the deployment of telecommunication networks and audiovisual services, the distribution of digital contents is getting more and more problematic in terms of intellectual-property rights. Indeed, copying of large-size digital files, and large-scale distribution of digital files, has become both easy and practically costless for individuals. Therefore, industries whose profit derives from the sales and distribution of digital data (such as music, video, electronic books, videogames, and so on) need protecting those data against uses which do not obey the rules set down in commercials agreements between providers and consumers of digital content. Such protection systems are called “Digital Rights Management” (DRM).
Simple CD and DVD authentication schemes rely on human assessment, e.g., by observing the quality and integrity of the packaging and the presentation of a product. More sophisticated mechanisms that are sometimes used in digital-content distribution make use of advanced printing techniques to resist forgery and duplication, and/or certificates of purchase, and/or the use of registration numbers on the packaging of a product. Such a registration number may be linked to the specific copy of the digital-content storage means, it can be verified during the installation process or it may be checked online.
Such techniques however assume that the registration number is only available to the legitimate owner of the digital-content storage means. If the registration number is supplied by the legitimate recipient to some other user to go with an illicit copy of these storage means, then authenticity checks that depend on the action of the user are of little use.
There are two known ways (possibly used in conjunction with one another) to resist forgery or unauthorized duplication of a product; the first is to make the content inaccessible (i.e. encrypted) so that copied content is unintelligible, while the second is to provide a process of authentication for the storage means (for example, a CD or a DVD) of the digital content, so that only after authentication has been successful can the content be accessed.
A known content-protection system using encryption works as follows. Each device manufacturer provides a copy of a secret machine-specific key to the content distributors. When content is printed on a CD, the content is encrypted using a secret session key s. This key s is then in turn encrypted under every device manufacturer key m and the results ENCm(s) are stored on the CD. At the time of playing the CD, the necessary encrypted session key ENCm(s) is selected from the disc and the content encryption key s, and hence the content, is recovered. The security of the scheme, the protection of the content and the authentication of the disc, depends on the fact that:                each device manufacturer shares a secret key with the content distributors;        the encrypted copies of the per-disc content keys ENCm(s) are stored on the CD in such a way that they cannot be copied by a malicious user; a part which cannot be copied of the CD playing surface is used for that purpose.        
The main limitation of such schemes is that symmetric keys have to be managed and shared by the device manufacturers and the content distributors. Given the difficulty of upgrading the keys in devices that are already commercialized, and the increased level of exposure due to having symmetric keys deployed at several different sites, such encryption schemes are rather inconvenient.
Some classically known solutions for authentication of a “prover” entity by a “verifier” entity are based on symmetric-key algorithms such as the well-known “Advanced Encryption Standard” AES (Standard FIPS 197 published by the National Institute of Standards and Technology); but such solutions suffer from the above-mentioned limitations of managing and sharing symmetric keys. Some other known solutions for authentication are based on public-key algorithms, such as DSA (“Digital Signature Algorithm”, Standard FIPS 186-2 published by the National Institute of Standards and Technology) or RSA (for a detailed description of RSA, see the article by R. L. Rivest, A. Shamir, and L. M. Adleman titled “A Method for Obtaining Digital Signatures and Public-key Cryptosystems”, Communications of the ACM, pages 120-126, volume 21, number 2, 1978). These classical solutions, whether based on symmetric keys or on public-key, are however inconvenient because they require additional circuitry in the verifier device, and furthermore require intensive computations, which implies that the verifier device must operate with a powerful (crypto-)processor.
Some other known authentication algorithms, by contrast, can be used in such a manner that some device which is relatively less powerful (computationally speaking) plays the role of the prover, and a more powerful device plays the role of the verifier. Such algorithms are of particular interest to deployments that use computationally-weak prover devices such as RFID tags communicating with much more powerful verifier devices such as tag-readers. An example of such a cryptographic algorithm is the GPS algorithm (for a detailed description of several variants of GPS, see for example International Standards ISO/IEC 9798-5 and 14888-2).
As is well-known in the art, one way to reduce computations in a device during an authentication protocol is—whenever applicable—by the use of cryptographic “coupons”. A coupon comprises, first, a randomly chosen number r and, second, a “reduced-coupon” x such that x=ƒ(r), where ƒ is a one-way function the calculation of which requires intensive computations (such as modular exponentiations). An example of such a cryptographic algorithm is DSA, wherein x=(gr mod p) mod q, where p and q are prime numbers and g is an integer derived from p and q; another example is a particular variant of GPS, wherein x=gr mod n, where n is a large integer, and g is an integer (typically much) smaller than n. Whenever a computationally-weak prover device takes part in a cryptographic protocol using such an algorithm, it may use a coupon in order to reduce computations, thereby significantly reducing the duration of the protocol.
Usually, a set of coupons (r,x) is loaded in the coupon-consuming device during the device fabrication process. Once this set of coupons has been consumed, one may either simply throw away the device if its cost of fabrication is low enough, or have the coupon-consuming device itself compute a new set of coupons, or else have a computationally-powerful device compute a new set of coupons which are then loaded in the coupon-consuming device.
However, it must be born in mind that the number of successive protocols in which a coupon-consuming device can enter is limited by the amount of memory required for storing the coupons. It is hence desirable to reduce the amount of memory occupied by each coupon. Such an improvement is actually known: it consists in storing in the coupon-consuming device during the fabrication process a set of reduced-coupons xi=ƒ(ri) (where i is an index for labeling the coupon), but not the corresponding random numbers ri, which are, instead, successively (viz., keeping with successive values of the index i) regenerated in the device whenever needed for taking part in a cryptographic protocol. This may be achieved for example by having the device calculate ri=PRFK(i), where K is a “regeneration key” owned by the device, and PRF is a keyed pseudo-random function the calculation of which requires only light computations.
One may then consider the possibility of reloading a coupon-consuming device with a set of reduced-coupons, by connecting it to a computationally-powerful reloading device. Such a solution has however never been implemented, because the communications environment is, in most practical deployments, insufficiently secured. There exists indeed a danger that a device may inadvertently request reloading from a fake or compromised coupon-reloading device, which will attempt to provide phony, arbitrarily chosen “reduced-coupons”. Since an attacker does not know the secret key K used in the calculation of the pseudo-random function PRFK, it is unable to calculate the pseudo-random numbers ri=PRFK(i); thus, any such “reduced-coupon” subsequently used by the coupon-consuming device during a cryptographic protocol with a verifier device, will be computationally unrelated to the number ri concurrently used. This amounts to a so-called “denial-of-service” attack, since it essentially disrupts the regular operation of the coupon-consuming device after reloading.